
#define MAX(a, b) ((a > b)? a: b)

typedef struct operacion {
	int id;
	int costo;
	int r; //tam del camino mas largo hasta ella desde el inicio
	int t; //tam del camino mas largo desde ella hasta el fin
	int maquina; //maquina a la que pertenece la operacion
	struct operacion *pj;
	struct operacion *sj;
	struct operacion *pm;
	struct operacion *sm;
} operacion;


typedef struct cromosoma {
  int * genes;
  int makespan;
} cromosoma;

typedef struct poblacion {
  cromosoma* pobla;
  int tam;
} poblacion;



/* Inicializa y almacena la poblacion inicial aleatoria, de tamano pop_size*/
int ini_poblacion(poblacion** p, int pop_size);

/* Selecciona tam_sel individuos de la poblacion pop.
 * Se le asigna un rango de probabilidad a cada individuo
 * en funcion a su costo. Luego se hace ruleta para escoger
 * los individuos seleccionados.
 */
poblacion * seleccionar_ruleta(poblacion* pop, int tam_sel);


/* Dada la poblacion pop, hace cruces con probabilidad
 * prob_cruce hasta generar sus hijos.
 * Cada padre se reproduce 2 veces 
 */
poblacion * reproducir(poblacion * pop, float prob_cruce, int);

/*
 * Cruza dos cromosomas y produce un hijo. Se genera un string
 * aleatorio de 0s y 1s que representa de que padre se deben
 * tomar los genes.
 */
cromosoma *cruzarPPX(cromosoma *p0, cromosoma *p1);

/* Dado un cromosoma, calcula y almacena el tiempo
 * que tarda en ejecutarse la planificacion que representa
 */
int set_makespan(cromosoma* xy);

/*
 * Calcula el costo de todos los cromosomas de una poblacion.
 * Devuelve el de mejor costo.
 */
cromosoma * update_makespans(poblacion * p);

/*
 * Muta una ploblacion haciendo intercambios (swaps) de genes. Cada
 * cromosoma puede ser mutado una sola vez, con probabilidad prob_mutar.
 *
 */
void mutar(poblacion * sanos, float prob_mutar);

/*
 * Reemplaza los peores individuos de la poblacion "grande" por 
 * los individuos de la poblacion "peq". El tamano de la poblacion
 * se mantiene constante.
 */
void reemplazo(poblacion * grande, poblacion * peq);


/*
 * Convierte una planificacion representada como una matriz, 
 * donde las filas son maquinas y las columnas son el orden
 * de las operaciones en esas maquinas, a un cromosoma.
 */
cromosoma * schedule_a_cromosoma(operacion*** in);

/* Convierte un cromosoma en una planificacion representada como una
 * matriz donde las filas son las maquinas y las columnas son las operaciones
 * que se ejecutan en esas maquinas en orden.
 */
operacion *** cromosoma_a_schedule(cromosoma* in);


/* Modelo de Algoritmo genetico estacionario
 * Seleccion por ruleta
 * Tamano de poblacion constante
 *
 */
int genetic_algorithm(int);





/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *archivo) ;

/// Local Search ////


/* Busqueda local mejor-mejor sobre solucion.
 * Devuelve el costo de la mejor solucion encontrada.
 */
 int local_search (operacion ***solucion) ;


/* Calcula los nodos que estan en el camino critico y
 * guarda el id de cada uno en un arreglo llamado nodos
 * Parametros:
 *		nodos: arreglo que contiene los id de las operaciones que se encuentran
 *			   en el camino critico
 *		solucion: matriz que representa el orden de operaciones en las maquinas
 *              posiciones: hash que dado un id de operacion, dice la ubicacion en el
 *                          schedule
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		cantidad de operaciones del camino critico
 */
int camino_critico(int ** nodos, operacion *** solucion, int *posiciones, int costo_sol, int r_sol[], int t_sol[]);


/*
 * Calcula el earliest starting time de la operacion op segun la planificacion que 
 * representa (operacion *** solucion).
 * Como el calculo es recursivo, se guardan los valores ya calculados en operaciones_est
 * de tal manera a no volverlos a calcular.
 */
int calcular_r (operacion ***solucion, int *posiciones, int operaciones_est[], operacion *op);


/*
 * Calcula el tiempo mas tarde en que op puede comenzar, sin atrasar la planificacion
 * Como es recursivo el calculo, se guarda en colas[] los valores que ya han sido
 * calculados.
 */
int calcular_t(operacion ***solucion, int *posiciones, int colas[], operacion *op );

/*
 * Calcula el costo de una planificacion, siendo este el tiempo que tarda en completarse
 * todos los trabajos.
 * in:
 *    solucion        matriz que representa la planificacion. cada fila es una maquina
 *    posiciones      hash que indica dado una operacion, en que punto de la planificacion
 *                    se encuentra.
 *    operaciones_est tiempo mas temprano de comienzo de cada operacion.
 *    colas           tiempo mas tarde de comienzo (sin retrasar la planificacion).
 */
  int costo_solucion (operacion ***solucion, int *posiciones, int *operaciones_est, int *colas);


/* Ejecuta el movimiento de las operaciones que se encuentran en el orden
 * representado por el arreglo actual para que queden en el orden representado
 * por el arreglo movimiento
 * Parametros:
 *              solucion: matriz que representa la planificacion. las filas son maquinas.
 *              posiciones: hash que dado una operacion, da la ubicacion en la planific.
 *		actual: arreglo que representa el orden actual de las operaciones
 *				involucradas en el movimiento
 *		movimiento: arreglo que representa el orden de las operaciones
 *					despues de ejecutar el movimiento
 *		tam_movimiento: cantidad de operaciones involucradas en el movimiento
 */
void hacer_movimiento (operacion ***solucion, int *posiciones, operacion *actual[], operacion *movimiento[], int tam_movimiento);

/* Calcula el movimiento que se debe realizar para obtener el mejor vecino
 * segun la vecindad N1
 * Parametros:
 *              solucion: matriz que representa una planificacion. Las filas
 *                       corresponden a las maquinas.
 *              posiciones: hash de operaciones a su ubicacion en la planificacion.
 *		primeros: arreglo de operaciones iniciales de cada maquina
 *		ultimos: arreglo de operaciones finales de cada maquina
 *		costo_sol: entero que representa el costo de la solucion
 *		r_sol: arreglo de tiempos de comienzo mas temprano de cada operacion
 *		t_sol: arreglo de tiempos desde que termina cada operacion hasta que
 *			   finalizan todos los trabajos
 * Valor de retorno:
 *		-1 en caso de no encontrar algun vecino que no esta prohibido
 *		en otro caso, cantidad de operaciones involucradas en el mejor movimiento
 */
  int mejor_movimiento_n1 (operacion ***solucion, int *posiciones, operacion *actual[], operacion *mejor[], operacion ** primeros, operacion ** ultimos, int costo_sol, int r_sol[], int t_sol[]);



